The present invention is related to network communications. More particularly, this specification discloses a method and apparatus for the generation and maintenance of a wireless ad-hoc network for multicasting real-time constant-bit-rate (CBR) data among a plurality of nodes.
Wireless ad-hoc networks consist of collections of xe2x80x9cpeerxe2x80x9d mobile nodes, capable of communicating with each other, and forming a dynamically changing network with no infrastructure. In order to route packets to a destination node, each node in a wireless ad-hoc network uses other nodes in the network as relays. Therefore, it is desirable that the nodes in the network establish routing among themselves, and that the routes keep changing as the nodes move, or as the environment changes due to such factors as fading and interference. Many routing protocols have been proposed to enable effective routing in such an environment, examples of which are provided in the articles cited below. In particular, multicasting has received much attention in the Internet community. Most of the development in multicast protocols, however, has addressed wireline, fixed networks having static topologies, and are focused toward Internet applications. The majority of these Internet multicast protocols do not consider the issue of resource reservation, because the available bandwidth is generally not a problem in wireline networks. Recently, the Core-Assisted Mesh Protocol (CAMP) was proposed for effective wireless multicasting of datagram traffic. However, CAMP neither supports real-time traffic nor does it attempt to guarantee any level of quality of service (QoS). No protocol developed to date addresses multicast streaming of real-time data in a wireless ad-hoc network environment.
Most multicast protocols result in the formation of a multicast structure, which is used for transportation of multicast data. Some schemes utilize core nodes or rendezvous points, which are used to collect multicast data from sources (if there are more than one) and then to multicast the data from these nodes to the receivers. The structure built may have the form of a tree or a mesh.
QoS is currently a focal point of attention in both wireline and wireless networks. There are two major ideologies for delivering QoS guarantees: the integrated services model and the differentiated services model. The integrated services model attempts to provide a guaranteed notion of service, which involves reserving bandwidth from the source node to the destination node. RSVP is a signaling protocol, which supports reservation of resources for multicast sessions on the Internet, is part of the integrated services specification. On the other hand, the differentiated services model is based on assigning resources to a user or edge router on a quasi-static basis. The resource is thus reserved based on what is called a service level agreement (SLA) and is then used to carry multiple classes of data. Each class of data receives a particular quality of service in terms of per-hop forwarding at each router. While, the differentiated services model is much simpler to implement than the integrated services model, it does not provide strict end-to-end quality of service guarantees in terms of bandwidth or delay.
Presently, there is a need for a multicasting method and system that is capable of supporting real-time CBR data among the nodes of a wireless network. It is also desirable that the system be distributed, highly adaptive to variations, flexible, and scalable.
References:
1. C. E. Perkins and P. Bhagwat, xe2x80x9cHighly dynamic Destination-Sequenced Distance Vector routing (DSDV) for mobile computersxe2x80x9d, Proceedings of SIGCOMM""94;
2. J. Broch et al, xe2x80x9cA Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocolsxe2x80x9d, Proceedings of MOBICOM""98;
3. D. Waitzmann, S. Deering and C. Partridge, xe2x80x9cDistance vector multicast routing protocolxe2x80x9d, RFC1075 (1988);
4. A. J. Ballardie, P. F. Francis and J. Crowcroft, xe2x80x9cCore Based Treesxe2x80x9d, in Proceedings of ACM SIGCOMM, 1993;
5. J. J. Garcia-Luna-Aceves and E. L. Madruga, xe2x80x9cA multicast routing protocol for ad-hoc networksxe2x80x9d, in Proceedings INFOCOM, 1999
6. P. Ferguson and G. Hutson, xe2x80x9cQuality of Service: Delivering QoS on the Internet and in Corporate Networksxe2x80x9d, John Wiley and Sons, Inc. 1998;
7. P. P. White, xe2x80x9cRSVP and integrated services on the Internet: a tutorialxe2x80x9d, IEEE Commun. Magazine, vol. 35, pp. 100-6, May 1997; and
8. http://pcl.cs.ucla.edu/projects/parsec/.
A real-time multicast scheduler method and apparatus is presented, to facilitate multicasting of real-time constant bit rate data in wireless ad-hoc networks. Constant bit rate traffic cannot tolerate delay jitter. However, a small amount of packet losses may be tolerable. In order to ensure the provisioning of a desired level of quality of service, bandwidth is reserved on the multicast structure. A goal of the real-time multicast scheduler is to avoid packet collisions and to facilitate color re-use, where xe2x80x9ccolorxe2x80x9d is defined as a channel selected as a combination of time-division multiple access (TDMA), frequency-division multiple access (FDMA), and code-division multiple access (CDMA) schemes. The real-time multicast scheduler provides a self-healing network which corrects for disconnections caused by node movement and nodes moving out of range of each other, while accounting for colors already assigned for data transmission in order to prevent packet collisions.
Provided is a method for bandwidth reservation for real-time traffic in a wireless ad-hoc network that includes a plurality of nodes transmitting and receiving data via a plurality of colors. The transmitting and receiving of the data is performed periodically with a data period p. Each one of the nodes has either a connected, disconnected, or a temporarily disconnected connection state, and the plurality of nodes includes a communication origin node from which a data transmission occurs. Each node is further defined as having a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node. In what follows, the identification of a node is denoted the node ID.
The reservation method comprises the steps of:
a. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node ID of a parent node from which disconnected node seeks to receive, the frame position fp of the disconnected maintenance transmitting node, and the color in which the disconnected maintenance packet transmitting disconnected node seeks to receive;
b. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node ID of the parent node from which connected node is currently receiving, the frame position fp of the node transmitting the connected maintenance packet, the color in which the connected maintenance packet transmitting node receives, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;
c. periodically transmitting a temporarily disconnected maintenance packet from each temporarily disconnected node, with each temporarily disconnected maintenance packet including the node ID of the temporarily disconnected maintenance packet transmitting node, the node ID of the parent node from which temporarily disconnected node seeks to receive, the frame position fp of the node transmitting the temporarily disconnected maintenance packet, the color in which the temporarily disconnected maintenance packet transmitting node seeks to receive, a set of the usable colors in which the temporarily disconnected node is transmitting, and a set of unusable colors in which the temporarily disconnected node is prohibited from transmitting;
d. receiving, at each particular node of the plurality of nodes, the maintenance packets from all nodes within a transmission range of the particular node;
e. using the maintenance packets received at each particular node to update the set of usable colors and the set of unusable colors for the particular node, where the set of usable colors for the particular node is defined as the complement of the set of unusable colors, and where the set of unusable colors of a first node Na having frame position fpa includes color ca if there is at least one other node Nb within transmit range of the first node Na, having frame position fpb, where Nb is not a child of node Na, where Nb receives at color ca, and where (fpa+1) mod p=fpb mod p where p represents the data period p; and
f. establishing data connections for the disconnected nodes Nd and temporarily disconnected nodes Nd, where a node Nd can connect to a node Nc with color cd within a transmission range of the node Nd, and with a minimum frame position fpc=fpdxe2x88x921 only if node Nc can transmit at color cd, where color cd=color ca as determined in step e, and only if color cd is not a transmit color of any other node Nk with frame position fpk within the transmission range of the first node Nd, such that fpc mod p=fpk mod p where p represents the data period p;
g. periodically repeating steps a through f to update the ad-hoc network.
The method of the present invention further includes the provision of a wireless ad-hoc network having the characteristics described for use with the reservation method.
The apparatus of the present invention includes a wireless ad-hoc network structure developed and maintained by the reservation method described above as well as the supporting hardware, i.e. a plurality of wireless ad-hoc network having the characteristics described for use with the reservation method.
The term xe2x80x9ccolorsxe2x80x9d used herein in the method and apparatus of the present invention are channels developed from TDMA, CDMA, and FDMA schemes or from combinations thereof.